package leetcode_top;

import org.junit.*;

public class Ex14 {

    @Test
    public void test() {
        Solution s = new Solution();
       String[] strs = {"dog","dracecar","dcar"};
       System.out.println(s.longestCommonPrefix(strs));
        
    }
    class Solution {
        public String longestCommonPrefix(String[] strs) {
            String res = strs[0];
            int len = res.length(), curLen;
            StringBuilder sb;
            for (int i = 0; i < strs.length; i++) {
                curLen = strs[i].length();
                len = Math.min(len , curLen);
                sb = new StringBuilder();
                for (int j = 0; j < len; j++) {
                    if (res.charAt(j) == strs[i].charAt(j)) {
                        sb.append(res.charAt(j));
                    } else break;
                }
                res = sb.toString();
                len = res.length();
            }
            return res;
        }
    }

    class Solution3 {
        public String longestCommonPrefix(String[] strs) {
            return divide(0, strs.length - 1, strs);
        }

        public String divide(int lo, int hi, String[] strs) {
            if (lo == hi) {
                return strs[lo];
            }
            int mid = (hi - lo) / 2 + lo;
            String left = divide(lo, mid, strs),
            right = divide(mid + 1, hi, strs);
            return merge(left, right);
        }

        public String merge(String left, String right) {
            int len1 = left.length(), len2 = right.length();
            len1 = Math.min(len1, len2);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len1; i++) {
                if (left.charAt(i) == right.charAt(i)) {
                    sb.append(left.charAt(i));
                } else break;
            }
            return sb.toString();
        }
    }
}
